from models import Page, TreeRoot
import re
from django.core.cache import cache


def clear_tree_caches():
    """
    Clear cached tree.
    """
    cache.delete('tree_navigation')
    
def is_page_under(over, under):
    """
    Is page a under page b in the tree.
    """   
    parent = find_parent(under)
    if parent is not None:
        if parent == over:
            return True
        else:
            is_page_under(over, parent)
    else:
        return False

def find_parent(page):
    """
    Returns a page's parent if it has one.
    """
    try:
        page.parent
        return page.parent
    except Page.DoesNotExist:
        try:
            return find_parent(page.left_sibling)
        except Page.DoesNotExist:
            return None

    
def get_root():
    """
    Returns the root of the tree or none if no root is set.
    """
    try:
        root = TreeRoot.objects.get(id=1)
        return root.page
    except TreeRoot.DoesNotExist:
        return None
        
def set_root(page):
    """
    Set tree root.
    """
    try:
        root = TreeRoot.objects.get(id=1)
        root.page = page
        root.save()
    except TreeRoot.DoesNotExist:
        root = TreeRoot(page=page)
        root.save()

def get_root_pages():
    """
    Returns the root node and its siblings.
    """
    root_pages = []

    root = get_root()
    if root is not None:

        next_sibling = root.sibling
        i = 0
        while next_sibling is not None:
            root_pages.append(next_sibling)
            next_sibling = next_sibling.sibling

    return root_pages
    


def insert_page(parent, page):
    """
    Insert page into the tree under parent.
    """
    if parent is None:
        root = get_root()
        if root is not None:
            sibling = find_last_sibling(root)
            sibling.sibling = page
            sibling.save()
        else:
            set_root(page)
    
    elif parent.child is None:
        parent.child = page
        parent.save()
    else:
        sibling_page = find_last_sibling(parent.child)
        sibling_page.sibling = page
        sibling_page.save()
    
    clear_tree_caches()
        

    

def destructive_move_page(parent, page):
    """
    Moves page to another parent without rebuilding the tree.
    """
    remove_related_pages(page)
    insert_page(parent, page)

def destructive_move_page_to_root(page):
    """
    Moves page to root level without rebuilding the tree.
    """
    remove_related_pages(page)
    root = get_root()
    if root is not None:
        insert_page(None, page)
    else:
        set_root(page)
        
def remove_related_pages(page):
    """
    Removes sibling and child from page.
    """
    page.sibling = None;
    page.child = None;
    page.save()
     

def remove_page_from_tree(page):
    """
    Removes a page from the tree and rebuilds the tree.
    """
    root = get_root()
    if page == root:
        if page.child is not None:
            set_root(page.child)
            if page.child.sibling is not None and page.sibling is not None:
                last_sibling = find_last_sibling(page.child)
                last_sibling.sibling = page.sibling
                last_sibling.save()
            elif page.sibling is not None:
                page.child.sibling = page.sibling
                page.child.save()
        
        elif page.sibling is not None:
            set_root(page.sibling)
              
    elif is_page_in_tree(page):
        prev_page = find_previous(page)
        if is_first_child(page):
            if page.sibling is not None and page.child is not None:
                prev_page.child = page.sibling
                last_sibling = find_last_sibling(page.sibling)
                last_sibling.sibling = page.child
                prev_page.save_unmodified()
                last_sibling.save_unmodified()
                
            elif page.sibling is not None:
                prev_page.child = page.sibling
                prev_page.save_unmodified()
            elif page.child is not None:
                prev_page.child = page.child
                prev_page.save_unmodified();
       
            else:
                prev_page.child = None
                prev_page.save_unmodified()
        else:
            if page.sibling is not None and page.child is not None:
                prev_page.sibling = page.sibling
                last_sibling = find_last_sibling(page.sibling)
                last_sibling.sibling = page.child
                prev_page.save_unmodified()
                last_sibling.save_unmodified()
                
            elif page.sibling is not None:
                prev_page.sibling = page.sibling
                prev_page.save_unmodified()
            elif page.child is not None:
                prev_page.sibling = page.child
                prev_page.save_unmodified()
            else:
                prev_page.sibling = None
                prev_page.save_unmodified()
            
        page.child = None
        page.sibling = None
        page.save_unmodified() 
        clear_tree_caches()       
        
def find_previous(page):
    """
    Finds the previous node in the tree.
    If there is no previous, return None
    """
    #First: try to find parent
    try:
        if page.parent is not None:
            return page.parent
    except Page.DoesNotExist:
        pass
    #Last: try to find left_sibling
    try:
        if page.left_sibling is not None:
            return page.left_sibling
    except Page.DoesNotExist:
        pass

    return None

def find_next(page):
    """
    Finds the next node in the tree.
    If there is no next, return None
    """
    #First: try to find child
    try:
        if page.child is not None:
            return page.child
    except Page.DoesNotExist:
        pass
    #Second: try to find sibling
    try:
        if page.sibling is not None:
            return page.sibling
    except Page.DoesNotExist:
        pass
    #Last: try to find parents sibling
    try:
        next = find_parent(page)
        if next is not None and next.sibling is not None:
            return next.sibling
    except Page.DoesNotExist:
        pass

    return None
    
def is_first_child(page):
    """
    Is page the first child among the siblings.
    """
    try:
        page.parent
        return True
    except Page.DoesNotExist:
        return False
    
def is_page_in_tree(page):
    """
    Is page in the tree.
    """
    def tree_traversal(current_page, page):
        if current_page == page:
            return True
        elif current_page.child is not None and current_page.sibling is not None:
            return tree_traversal(current_page.child, page) or tree_traversal(current_page.sibling, page)
        elif current_page.child is not None:
            return tree_traversal(current_page.child, page)
        elif current_page.sibling is not None:
            return tree_traversal(current_page.sibling, page)
        else:
            return False
    
    root = get_root()
    if root is not None: 
        return tree_traversal(root, page)
    else:
        return False

def find_last_sibling(page):
    """
    Returns the last sibling of page
    """
    if page.sibling is None:
        return  page
    else:
        return find_last_sibling(page.sibling)

def tree_to_set():
    """
    Returns the current tree as a set
    """
    tree_set = set()
    next_page = get_root()
    while next_page is not None:
        tree_set.add(next_page.id)
        next_page = find_next(next_page)

    return tree_set

def save_tree(serialized_structure):
    """
    Parses the serialized page structure and saves the new tree.
    This method does not validate that the new structure is a valid tree.
    An input describing a broken structure will result in a broken tree.
    """
    partition =  serialized_structure.partition('&')
    
    #Get the new root, remove all it's relationships and set it as root
    r = re.match(r'\w+\[(\d+)\]=(\d+|null)', partition[0])
    page = Page.objects.get(id=r.group(1))
    remove_related_pages(page)
    set_root(page)

    for assignment in partition[2].split('&'):
        #Match: letters[(page_id)]=(page_id|null)
        m = re.match(r'\w+\[(\d+)\]=(\d+|null)', assignment)

        #Move pages
        if m.group(2) != 'null':
            parent = Page.objects.get(id=m.group(2)) 
            page = Page.objects.get(id=m.group(1))
            destructive_move_page(parent, page)
        else:
            page = Page.objects.get(id=m.group(1))
            destructive_move_page_to_root(page)
